{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Element-Sum of a Complete Subset of Indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完全子集的最大元素和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>1</strong> 开始、由 <code>n</code> 个整数组成的数组。</p>\n",
    "\n",
    "<p>如果一组数字中每对元素的乘积都是一个完全平方数，则称这组数字是一个 <strong>完全集</strong> 。</p>\n",
    "\n",
    "<p>下标集 <code>{1, 2, ..., n}</code> 的子集可以表示为 <code>{i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>k</sub>}</code>，我们定义对应该子集的 <strong>元素和</strong> 为 <code>nums[i<sub>1</sub>] + nums[i<sub>2</sub>] + ... + nums[i<sub>k</sub>]</code> 。</p>\n",
    "\n",
    "<p>返回下标集&nbsp;<code>{1, 2, ..., n}</code> 的 <strong>完全子集</strong> 所能取到的 <strong>最大元素和</strong> 。</p>\n",
    "\n",
    "<p>完全平方数是指可以表示为一个整数和其自身相乘的数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [8,7,3,5,7,2,4,9]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>除了由单个下标组成的子集之外，还有两个下标集的完全子集：{1,4} 和 {2,8} 。\n",
    "与下标 1 和 4 对应的元素和等于 nums[1] + nums[4] = 8 + 5 = 13 。\n",
    "与下标 2 和 8 对应的元素和等于 nums[2] + nums[8] = 7 + 9 = 16 。\n",
    "因此，下标集的完全子集可以取到的最大元素和为 16 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,10,3,10,1,13,7,9,4]\n",
    "<strong>输出：</strong>19\n",
    "<strong>解释：</strong>除了由单个下标组成的子集之外，还有四个下标集的完全子集：{1,4}、{1,9}、{2,8}、{4,9} 和 {1,4,9} 。 \n",
    "与下标 1 和 4 对应的元素和等于 nums[1] + nums[4] = 5 + 10 = 15 。 \n",
    "与下标 1 和 9 对应的元素和等于 nums[1] + nums[9] = 5 + 4 = 9 。 \n",
    "与下标 2 和 8 对应的元素和等于 nums[2] + nums[8] = 10 + 9 = 19 。\n",
    "与下标 4 和 9 对应的元素和等于 nums[4] + nums[9] = 10 + 4 = 14 。 \n",
    "与下标 1、4 和 9 对应的元素和等于 nums[1] + nums[4] + nums[9] = 5 + 10 + 4 = 19 。 \n",
    "因此，下标集的完全子集可以取到的最大元素和为 19 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-element-sum-of-a-complete-subset-of-indices](https://leetcode.cn/problems/maximum-element-sum-of-a-complete-subset-of-indices/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-element-sum-of-a-complete-subset-of-indices](https://leetcode.cn/problems/maximum-element-sum-of-a-complete-subset-of-indices/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,7,3,5,7,2,4,9]', '[5,10,3,10,1,13,7,9,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "test = [i * i for i in range(1, 101)]\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            res = 0\n",
    "            for j in test:\n",
    "                if i * j <= len(nums):\n",
    "                    res += nums[i * j - 1]\n",
    "                else:\n",
    "                    break\n",
    "            ans = max(ans, res)\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, A: List[int]) -> int:\n",
    "        return max(sum(A[d * x * x - 1]\n",
    "                       for x in range(1, isqrt(len(A) // d) + 1))\n",
    "                   for d in range(1, len(A) + 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, A: List[int]) -> int:\n",
    "        return max(sum(A[d * x * x - 1]\n",
    "                       for x in range(1, isqrt(len(A) // d) + 1))\n",
    "                   for d in range(1, len(A) + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        i = 1\n",
    "        n = len(nums)\n",
    "        ls = []\n",
    "        while i*i <= n:\n",
    "            ls.append(i*i)\n",
    "            i += 1\n",
    "        res = max(sum(nums[i-1] for i in ls),max(nums))\n",
    "        #print(ls,res)\n",
    "        for j in range(2,n):\n",
    "            o = []\n",
    "            for i in range(len(ls)):\n",
    "                if ls[i]*j<=n:o.append(ls[i]*j)\n",
    "                else:break\n",
    "            #print(o)\n",
    "            if len(o)==1:break\n",
    "            #print(o,nums)\n",
    "            res = max(sum(nums[i-1] for i in o),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import os\n",
    "from typing import *\n",
    "from functools import lru_cache\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idxs = []\n",
    "        for i in range(1, n+1):\n",
    "            r = i * i\n",
    "            if r > n:\n",
    "                break\n",
    "            idxs.append(r)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            s = 0\n",
    "            for idx in idxs:\n",
    "                ni = idx * i\n",
    "                if ni > n:\n",
    "                    break\n",
    "                s += nums[ni-1]\n",
    "            res = max(res, s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        def core(num):\n",
    "            if num < 4:\n",
    "                return num\n",
    "\n",
    "            i = 2\n",
    "            while i < sqrt(num) + 1:\n",
    "                if (num / pow(i,2)) % 1 == 0:\n",
    "                    num = num // pow(i,2)\n",
    "                    i = 2\n",
    "                    continue\n",
    "                i += 1\n",
    "            return num\n",
    "        \n",
    "        ans = [0] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            ans[core(i+1)] += nums[i]\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        square = [i * i for i in range(1, 200) if i * i <= n]\n",
    "        # print(square)\n",
    "        ans = max(nums)\n",
    "        for i in range(1, n+1):\n",
    "            tmp = 0\n",
    "            for sq in square:\n",
    "                if i * sq > n:\n",
    "                    break\n",
    "                tmp += nums[i * sq - 1]\n",
    "            \n",
    "            ans = max(ans, tmp)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l0 = []\n",
    "        for i in range(1, n + 1):\n",
    "            if i * i > n:\n",
    "                break\n",
    "            l0.append(i * i)\n",
    "        ans = 0\n",
    "        for j in range(1, n + 1):\n",
    "            tmp = 0\n",
    "            for i in l0:\n",
    "                if j * i > n:\n",
    "                    break\n",
    "                tmp += nums[j * i - 1]\n",
    "            ans = max(ans, tmp)   \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        s=[]\n",
    "        \n",
    "        n=len(nums)\n",
    "        # d={}\n",
    "        # lh=[1]\n",
    "        maxa=0\n",
    "        a=0\n",
    "        for j in range(1,n+1):\n",
    "            if j**2<=n:\n",
    "                a=a+nums[j**2-1]\n",
    "                s.append(j**2)\n",
    "        maxa=a\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            if i in s:\n",
    "                continue\n",
    "            # d[i]=[i]\n",
    "            a=nums[i-1]\n",
    "            for j in range(2,int(sqrt((n/i)))+1):\n",
    "                if True:                                               \n",
    "                    if (i*j*j<=n):\n",
    "                        # d[i].append(i*j*j)  \n",
    "                        a=a+nums[i*j*j-1]     \n",
    "            maxa=max(maxa,a)             \n",
    "                        \n",
    "        ll=[]\n",
    "        # for i in d:\n",
    "            \n",
    "        #     p=list(set(d[i]))\n",
    "        #     maxa=max(maxa,sum([nums[j-1]for j in p]))\n",
    "\n",
    "        # maxa=max(maxa,a)     \n",
    "            \n",
    "        # print(maxa,n,d,s,a)\n",
    "        return maxa\n",
    "               \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sq = [i**2 for i in range(1,101)]\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        def getprem(num):\n",
    "            n1, n2 =[], []\n",
    "            for i in range(1, int(num**0.5)):\n",
    "                if num%i == 0:\n",
    "                    n1.append(i)\n",
    "                    n2.append(num//i)\n",
    "            return n1, n2\n",
    "        multi = 1\n",
    "        ans = max(nums)\n",
    "        while(multi*4 <=len(nums)):\n",
    "            ans = max(ans , sum(nums[i*multi-1] for i in sq if i*multi<=len(nums)))\n",
    "            multi+=1\n",
    "        for j in sq:\n",
    "            if j>len(nums)**2:\n",
    "                break\n",
    "            n1, n2 = getprem(j)\n",
    "            for i, k in zip(n1,n2):\n",
    "                if i-1>=len(nums) or k-1>=len(nums):\n",
    "                    continue\n",
    "                ans = max(ans, nums[i-1]+nums[k-1])\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            res = 0\n",
    "            for j in count(1):\n",
    "                idx = (i + 1) * j * j - 1\n",
    "                if idx >= n: break\n",
    "                res += nums[idx]\n",
    "            ans = max(ans, res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(1,n+1):\n",
    "            s = 0\n",
    "            for j in range(1,isqrt(n//i)+1):\n",
    "                s+=nums[i*j*j-1]\n",
    "            ans = max(ans,s)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        # 枚举\n",
    "        pass\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            #i 为当前最大值\n",
    "            s = 0\n",
    "            # i * j * j 为同组数据，IJJ *iJJ 肯定是满足完全平方\n",
    "            for j in range(1, isqrt(n // i) + 1):\n",
    "                s += nums[i * j * j - 1]  # -1 是因为数组下标从 0 开始\n",
    "            ans = max(ans, s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# core(x) x除去「偶数数量质因数」后 的质因数的乘积\n",
    "# 一组数字中每对元素的乘积都是一个完全平方数 每个数的core是相同的\n",
    "# core(1): 1, 4, 9, 16, 25, 36...\n",
    "# core(2): 2*1, 2*4, 2*9, 2*16...\n",
    "# core(3): 3*1, 3*4, 3*9, 3*16...\n",
    "# core(i): i*1, i*4, i*9, i*16...\n",
    "# i * j * j <= n   ->    j <= isqrt(n // i)\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1): # 可能是质数 所以枚举到n\n",
    "            s = 0\n",
    "            for j in range(1, isqrt(n // i) + 1):\n",
    "                s += nums[i * j * j - 1]\n",
    "            ans = max(ans, s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        def core(n):\n",
    "            res = 1\n",
    "            for i in range(2, int(sqrt(n)) + 1):\n",
    "                e = 0\n",
    "                while n % i == 0:\n",
    "                    e ^= 1\n",
    "                    n //= i\n",
    "                if e:\n",
    "                    res *= i\n",
    "            if n > 1:\n",
    "                res *= n\n",
    "            return res\n",
    "        ans = [0 for _ in range(len(nums) + 1)]\n",
    "        for i, v in enumerate(nums, 1):\n",
    "            ans[core(i)] += v\n",
    "        return max(ans)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(nums)\n",
    "        ret = []\n",
    "        for i in range(1, 1000):\n",
    "            cnt = 1\n",
    "            ret2 = []\n",
    "            gap = i\n",
    "            while gap * cnt ** 2 <= len1:\n",
    "                ret2.append(cnt ** 2 * gap)\n",
    "                cnt += 1\n",
    "            if len(ret2) == 0:\n",
    "                break\n",
    "            ret.append(ret2)\n",
    "        s1 = 0\n",
    "        for i in ret:\n",
    "            v1 = 0\n",
    "            for x in i:\n",
    "                v1 += nums[x - 1]\n",
    "            s1 = max(s1, v1)\n",
    "        return s1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(nums)\n",
    "        ret = []\n",
    "        for i in range(1, 1000):\n",
    "            cnt = 1\n",
    "            ret2 = []\n",
    "            gap = i\n",
    "            while gap * cnt ** 2 <= len1:\n",
    "                ret2.append(cnt ** 2 * gap)\n",
    "                cnt += 1\n",
    "            if len(ret2) == 0:\n",
    "                break\n",
    "            ret.append(ret2)\n",
    "        s1 = max(nums)\n",
    "        for i in ret:\n",
    "            v1 = 0\n",
    "            for x in i:\n",
    "                v1 += nums[x - 1]\n",
    "            s1 = max(s1, v1)\n",
    "        return s1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        s=[0]*(len(nums)+1)\n",
    "        for i,x in enumerate(nums,1):\n",
    "            s[core[i]]+=x\n",
    "        return max(s)\n",
    "\n",
    "MX=10001\n",
    "core=[0]*MX\n",
    "for i in range(1,MX):\n",
    "    if core[i]==0:\n",
    "        for j in range(1,isqrt(MX//i)+1):\n",
    "            core[i*j*j]=i\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# core(x) x除去「偶数数量质因数」后 的质因数的乘积\n",
    "# 一组数字中每对元素的乘积都是一个完全平方数 每个数的core是相同的\n",
    "core = [1] * (10 ** 4 + 1)\n",
    "for x in range(2, 10 ** 4 + 1):\n",
    "    num = x\n",
    "    for y in range(2, isqrt(x) + 1):\n",
    "        cnt = 0\n",
    "        while num % y == 0:\n",
    "            cnt += 1\n",
    "            num //= y\n",
    "        if cnt % 2 == 1: core[x] *= y\n",
    "    if num > 1: core[x] *= num\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = [0] * (n + 1) # 索引:core值 值:累积和\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            ans[core[i]] += x\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        result = int(math.sqrt(n))\n",
    "        ls = []\n",
    "        lst=[]\n",
    "        ans = 0\n",
    "        for i in range(1,result*2+1):\n",
    "            if i*i<=n:\n",
    "                ans+=nums[i*i-1]\n",
    "                lst.append(i*i)\n",
    "            if i in lst:\n",
    "                continue\n",
    "            k=1\n",
    "            if i>1:\n",
    "                for j in range(2,result*2):\n",
    "                    k=i*(j**2)\n",
    "                    while k<=n:\n",
    "                        if (i,k) not in ls:\n",
    "                            ls.append((i,k))\n",
    "                        k=k*(j**2)\n",
    "        ex = {}\n",
    "        for m,(x,y) in enumerate(ls):\n",
    "            if str(x) in ex:\n",
    "                ex[str(x)] = ex.get(str(x))+nums[y-1]\n",
    "            else:\n",
    "                ex[str(x)] = nums[x-1]+nums[y-1]\n",
    "        for key in ex:\n",
    "            ans = max(ans,ex.get(key))\n",
    "\n",
    "        ans = max(ans,max(nums))\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 10001\n",
    "core = [0 for _ in range(mx)]\n",
    "for i in range(1, mx):\n",
    "    if core[i]==0: # i 不含完全平方因子，可以作为core值\n",
    "        for j in range(1, isqrt(mx//i)+1):\n",
    "            core[i*j*j] = i\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0 for _ in range(n+1)]\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            s[core[i]] += x \n",
    "        return max(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        result = int(math.sqrt(n))\n",
    "        ls = []\n",
    "        lst=[]\n",
    "        i_res = []\n",
    "        ans = 0\n",
    "        for i in range(1,result*2+1):\n",
    "            if i*i<=n:\n",
    "                ans+=nums[i*i-1]\n",
    "                lst.append(i*i)\n",
    "            if i in lst:\n",
    "                continue\n",
    "            k=1\n",
    "            if i>1:\n",
    "                for j in range(2,n//2):\n",
    "                    k=i*(j**2)\n",
    "                    while k<=n:\n",
    "                        if (i,k) not in ls:\n",
    "                            ls.append((i,k))\n",
    "                        k=k*(j**2)\n",
    "        print(lst,ls,result,n)\n",
    "        ex = {}\n",
    "        for m,(x,y) in enumerate(ls):\n",
    "            if str(x) in ex:\n",
    "                ex[str(x)] = ex.get(str(x))+nums[y-1]\n",
    "            else:\n",
    "                ex[str(x)] = nums[x-1]+nums[y-1]\n",
    "        for key in ex:\n",
    "            ans = max(ans,ex.get(key))\n",
    "\n",
    "        ans = max(ans,max(nums))\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        core=[[]]*(n+1)\n",
    "        square=[]\n",
    "        for i in range(1,int(sqrt(n))+1):\n",
    "            square.append(i*i)\n",
    "        ans=0\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            temp=0\n",
    "            for x in square:\n",
    "                if i*x>n:\n",
    "                    break\n",
    "                core[i].append(i*x)\n",
    "                temp+=nums[i*x-1]\n",
    "            if temp>ans:\n",
    "                ans=temp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        data = {}\n",
    "        for i in range(1, n + 1):\n",
    "            x = i\n",
    "            now = 1\n",
    "            for j in range(2, int(sqrt(i)) + 1):\n",
    "                cnt = 0\n",
    "                while x % j == 0:\n",
    "                    cnt ^= 1\n",
    "                    x //= j\n",
    "                if cnt == 1:\n",
    "                    now *= j\n",
    "            if x != 1:\n",
    "                now *= x\n",
    "            if now not in data.keys():\n",
    "                data[now] = nums[i - 1]\n",
    "            else:\n",
    "                data[now] += nums[i - 1]\n",
    "        ans = 0\n",
    "        for key in data.keys():\n",
    "            ans = max(ans, data[key])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        定义core(x)是将x除去完全平方因子后的剩余结果，即x中所有出现次数为奇数的质因子相乘\n",
    "        那么要保证一个组中任意一对元素的乘积都是一个完全平方数，那么要保证这个组的core(x)都是一样的\n",
    "        \"\"\"\n",
    "        def core(x):\n",
    "            ans = 1\n",
    "            p = 2\n",
    "            while p * p <= x:\n",
    "                cnt = 0\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "                    cnt += 1\n",
    "                if cnt & 1:\n",
    "                    ans *= p\n",
    "                p += 1\n",
    "            if x > 1:\n",
    "                ans *= x\n",
    "            return ans\n",
    "        n = len(nums)\n",
    "        memo = defaultdict(int)\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            memo[core(i)] += x\n",
    "        return max(memo.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter()\n",
    "        for idx in range(1, n + 1):\n",
    "            p = 1\n",
    "            cur = idx\n",
    "            x = 2 \n",
    "            while x * x <= idx:\n",
    "                if cur % x == 0:\n",
    "                    cnt = 0\n",
    "                    while cur % x == 0:\n",
    "                        cnt ^= 1 \n",
    "                        cur //= x\n",
    "                    if cnt == 1:\n",
    "                        p *= x \n",
    "                x += 1\n",
    "            if idx > 1:\n",
    "                p *= cur \n",
    "            counter[p] += nums[idx - 1] \n",
    "        return max(counter.values())\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "\n",
    "        # 查找小于N的所有素数\n",
    "        l_p = [3]\n",
    "        n = 5\n",
    "\n",
    "        while n < N:\n",
    "            for p in l_p:\n",
    "                if n % p == 0:\n",
    "                    break\n",
    "                if p * p > n:\n",
    "                    l_p.append(n)\n",
    "                    break\n",
    "            n += 2\n",
    "\n",
    "        l_p.insert(0, 2)\n",
    "\n",
    "        # 乘以平方数，并求和\n",
    "        def calc(mul):\n",
    "            # print(mul)\n",
    "            l = []\n",
    "            n = 1\n",
    "\n",
    "            while 1:\n",
    "                n2 = n * n * mul\n",
    "                if n2 > N:\n",
    "                    break\n",
    "\n",
    "                n += 1\n",
    "                l.append(n2)\n",
    "\n",
    "            ret = 0\n",
    "            for i in l:\n",
    "                ret += nums[i - 1]\n",
    "            return ret\n",
    "\n",
    "        ret = max(calc(1), max(nums))\n",
    "\n",
    "        # 取n个素数相乘\n",
    "        # 最大值\n",
    "        M = N // 4\n",
    "\n",
    "        def get(n, mul, i):\n",
    "            l = [mul]\n",
    "            for j in range(i, n + i):\n",
    "                l.append(l[-1] * l_p[j])\n",
    "\n",
    "            if l[-1] > M:\n",
    "                return\n",
    "\n",
    "            yield l[-1]\n",
    "\n",
    "            # 每一位往后移\n",
    "            for j in range(n):\n",
    "                yield from get(j + 1, l[n - j - 1], i + n - j)\n",
    "\n",
    "        # print(N, M)\n",
    "\n",
    "        for n in range(1, len(l_p) + 1):\n",
    "            isok = False\n",
    "            for mul in get(n, 1, 0):\n",
    "                isok = True\n",
    "                ret = max(ret, calc(mul))\n",
    "\n",
    "            if not isok:\n",
    "                return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        #算下标\n",
    "        n=len(nums)\n",
    "        t=defaultdict(int)\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)+1):\n",
    "            f=1\n",
    "            j=2\n",
    "            while j*j<=i:\n",
    "                if i%(j*j)==0:\n",
    "                    f=j*j\n",
    "                j+=1\n",
    "            t[i//f]+=nums[i-1]\n",
    "            ans=max(ans,t[i//f])\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter()\n",
    "        for idx in range(1, n + 1):\n",
    "            p = 1\n",
    "            cur = idx\n",
    "            x = 2 \n",
    "            while x * x <= idx:\n",
    "                if cur % x == 0:\n",
    "                    cnt = 0\n",
    "                    while cur % x == 0:\n",
    "                        cnt ^= 1 \n",
    "                        cur //= x\n",
    "                    if cnt == 1:\n",
    "                        p *= x \n",
    "                x += 1\n",
    "            if idx > 1:\n",
    "                p *= cur \n",
    "            counter[p] += nums[idx - 1] \n",
    "        return max(counter.values())\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter()\n",
    "        for idx in range(1, n + 1):\n",
    "            p = 1\n",
    "            cur = idx\n",
    "            x = 2 \n",
    "            while x * x <= idx:\n",
    "                if cur % x == 0:\n",
    "                    cnt = 0\n",
    "                    while cur % x == 0:\n",
    "                        cnt ^= 1 \n",
    "                        cur //= x\n",
    "                    if cnt == 1:\n",
    "                        p *= x \n",
    "                x += 1\n",
    "            if idx > 1:\n",
    "                p *= cur \n",
    "            counter[p] += nums[idx - 1] \n",
    "        return max(counter.values())\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter()\n",
    "        for i in range(1, n + 1):\n",
    "            idx = i\n",
    "            p = 2 \n",
    "            cur = 1\n",
    "            while p * p <= idx:\n",
    "                if idx % p == 0:\n",
    "                    cnt = 0\n",
    "                    while idx % p == 0:\n",
    "                        cnt ^= 1 \n",
    "                        idx //= p \n",
    "                    if cnt == 1:\n",
    "                        cur *= p \n",
    "                p += 1 \n",
    "            if idx > 1:\n",
    "                cur *= idx \n",
    "            counter[cur] += nums[i - 1]\n",
    "        return max(counter.values())\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache  # 保存 core(n) 的计算结果，测试用例之间可以复用\n",
    "def core(n: int) -> int:\n",
    "    res = 1\n",
    "    for i in range(2, isqrt(n) + 1):\n",
    "        e = 0\n",
    "        while n % i == 0:\n",
    "            e ^= 1\n",
    "            n //= i\n",
    "        if e:\n",
    "            res *= i\n",
    "    if n > 1:\n",
    "        res *= n\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        s = [0] * (len(nums) + 1)\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            s[core(i)] += x\n",
    "        return max(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache  # 保存 core(n) 的计算结果，测试用例之间可以复用\n",
    "def core(n: int) -> int:\n",
    "    res = 1\n",
    "    for i in range(2, isqrt(n) + 1):\n",
    "        e = 0\n",
    "        while n % i == 0:\n",
    "            e ^= 1\n",
    "            n //= i\n",
    "        if e:\n",
    "            res *= i\n",
    "    if n > 1:\n",
    "        res *= n\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        s = [0] * (len(nums) + 1)\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            s[core(i)] += x\n",
    "        return max(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX=10**4+5\n",
    "prime=[0 for i in range(MAX)]\n",
    "prime[1]=1\n",
    "for i in range(2,MAX):\n",
    "    if prime[i]==0:\n",
    "        prime[i]=i\n",
    "        for j in range(i+i,MAX,i):\n",
    "            if prime[j]==0:\n",
    "                prime[j]=1\n",
    "            k=j\n",
    "            m=0\n",
    "            while k%i==0:\n",
    "                k//=i\n",
    "                m^=1\n",
    "            if m==1:\n",
    "                prime[j]*=i\n",
    "class Solution:\n",
    "    def maximumSum(self, a: List[int]) -> int:\n",
    "        n=len(a)\n",
    "        ans={}\n",
    "        for i,j in enumerate(a):\n",
    "            ans[prime[i+1]]=ans.get(prime[i+1],0)+j\n",
    "        return max(ans.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def get(x: int) -> int:\n",
    "    res = 1\n",
    "    for i in range(2, isqrt(x) + 1):\n",
    "        if x % i == 0:\n",
    "            e = 0\n",
    "            while x % i == 0:\n",
    "                e += 1\n",
    "                x //= i\n",
    "            if e % 2 != 0:\n",
    "                res *= i\n",
    "    if x > 1:\n",
    "        res *= x\n",
    "    return res\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            s[get(i)] += x\n",
    "        return max(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache  # 保存 core(n) 的计算结果，测试用例之间可以复用\n",
    "def core(n: int) -> int:\n",
    "    res = 1\n",
    "    for i in range(2, isqrt(n) + 1):\n",
    "        e = 0\n",
    "        while n % i == 0:\n",
    "            e ^= 1\n",
    "            n //= i\n",
    "        if e:\n",
    "            res *= i\n",
    "    if n > 1:\n",
    "        res *= n\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        s = [0] * (len(nums) + 1)\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            s[core(i)] += x\n",
    "        return max(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def core(x : int) -> int:\n",
    "    p = 2\n",
    "    k = 0\n",
    "    res = 1\n",
    "    while p <= x:\n",
    "        if x % p == 0:\n",
    "            k += 1\n",
    "            x //= p\n",
    "        else:\n",
    "            if k > 0 and k % 2:\n",
    "                res *= p\n",
    "            k = 0\n",
    "            p += 1\n",
    "    if k > 0 and k % 2:\n",
    "        res *= p\n",
    "    return res\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        s = [0] * (len(nums) + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            s[core(i + 1)] += x\n",
    "        return max(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        def getPrimeFactors(n: int):\n",
    "            if n <= 1:\n",
    "                return tuple()\n",
    "            primes = Counter()\n",
    "            while n % 2 == 0:\n",
    "                primes[2] = (primes[2] + 1) % 2\n",
    "                n //= 2\n",
    "            for i in range(3, int(sqrt(n)) + 1, 2):\n",
    "                while n % i == 0:\n",
    "                    primes[i] = (primes[i] + 1) % 2\n",
    "                    n //= i\n",
    "            if n > 2:\n",
    "                primes[n] = (primes[n] + 1) % 2\n",
    "            return tuple([k for (k, v) in primes.items() if v > 0])\n",
    "        visited = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            f = getPrimeFactors(i + 1)\n",
    "            ans = max(ans, n)\n",
    "            if f in visited:\n",
    "                ans = max(ans, visited[f] + n)\n",
    "            # print(i, n, f, visited[f], ans)\n",
    "            visited[f] += n\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def core(n: int) -> int:\n",
    "    res = 1\n",
    "    for i in range(2,isqrt(n) + 1):\n",
    "        e = 0\n",
    "        while n % i == 0:\n",
    "            n //= i\n",
    "            e += 1\n",
    "        if e % 2:\n",
    "            res *= i\n",
    "    res *= n\n",
    "    return res\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            s[core(i + 1)] += x\n",
    "        return max(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "MAXN = 10001\n",
    "prims = []\n",
    "is_prims = [True] * MAXN\n",
    "min_prim = [None] * MAXN\n",
    "equiv = [None] * MAXN\n",
    "\n",
    "equiv[1] = 1\n",
    "\n",
    "for i in range(2, MAXN):\n",
    "    if is_prims[i]:\n",
    "        prims.append(i)\n",
    "        min_prim[i] = i\n",
    "        equiv[i] = i\n",
    "    for p in prims:\n",
    "        if p > min_prim[i] or p * i >= MAXN:\n",
    "            break\n",
    "        v = p * i\n",
    "        is_prims[v] = False\n",
    "        min_prim[v] = p\n",
    "        if p == min_prim[i]:\n",
    "            equiv[v] = equiv[i // p]\n",
    "        else:\n",
    "            equiv[v] = equiv[i] * p\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        groups = {}\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            e = equiv[i]\n",
    "            groups[e] = groups.get(e, 0) + nums[i - 1]\n",
    "        return max(groups.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        #return nums[0]\n",
    "        n = len(nums)\n",
    "        had = Counter()\n",
    "        ans = 0\n",
    "        #先求出n以内（包括n）的所有质数\n",
    "        # isPrime = [True] * (n + 1)\n",
    "        # for i in range(2, int(sqrt(n)) + 1):\n",
    "        #     if not isPrime[i]:\n",
    "        #         continue\n",
    "        #     for x in range(i * i, n + 1, i):\n",
    "        #         isPrime[x] = False\n",
    "        # ans = 0\n",
    "        # for i in range(1, int(sqrt(n)) + 1):\n",
    "        #     ans += nums[i*i-1]\n",
    "\n",
    "        for i in range(n):\n",
    "            minI = i + 1\n",
    "            #对minI进行质数分解\n",
    "            x = minI\n",
    "            base = 2\n",
    "            odd = []\n",
    "              \n",
    "            while base * base <= x:\n",
    "                cnt = 0\n",
    "                if x % base == 0:\n",
    "                    \n",
    "                    while x % base == 0:\n",
    "                        cnt += 1\n",
    "                        x //= base\n",
    "                if cnt % 2 == 1:\n",
    "                    odd.append(base)\n",
    "\n",
    "                base += 1\n",
    "            if x > 1:\n",
    "                odd.append(x)    \n",
    "\n",
    "            if odd == []:\n",
    "                odd = [1]\n",
    "            print(i, odd)\n",
    "            odd = tuple(odd)\n",
    "            had[odd] += nums[i]\n",
    "            \n",
    "        for key in had:\n",
    "            ans = max(ans, had[key])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        mp = collections.defaultdict(list)\n",
    "        for idx in range(1, len(nums)+1):\n",
    "            i = 2\n",
    "            ii = i*i\n",
    "            x = idx\n",
    "            while ii <= x:\n",
    "                if x % ii == 0:\n",
    "                    x //= ii\n",
    "                    continue\n",
    "                i += 1\n",
    "                ii = i*i\n",
    "            mp[x].append(idx)\n",
    "        res = 0\n",
    "        for k, v in mp.items():\n",
    "            cur = 0\n",
    "            for idx in v:\n",
    "                cur += nums[idx-1]\n",
    "            res = max(res, cur)\n",
    "        return res\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Primer(object):\n",
    "    \"\"\"素数相关运算的辅助类\n",
    "\n",
    "    Attributes:\n",
    "        1. n：用素数筛选法提前计算好的最大数\n",
    "        2. primes：n以内的所有素数列表\n",
    "        3. min_prime_factors：每个下标数的最小素因数（最小素因数不存在时为-1）\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    @property\n",
    "    def n(self):\n",
    "        return self._n\n",
    "\n",
    "    @property\n",
    "    def primes(self):\n",
    "        return self._primes\n",
    "\n",
    "    @property\n",
    "    def min_prime_factors(self):\n",
    "        return self._min_prime_factors\n",
    "\n",
    "    def __init__(self, n=100):\n",
    "        \"\"\"初始化\n",
    "\n",
    "        生成n以内的所有素数primes，同时得到每个数的最小素因数min_prime_factors\n",
    "\n",
    "        Time Complexity:\n",
    "            O(n)\n",
    "\n",
    "        \"\"\"\n",
    "        primes = []\n",
    "        min_prime_factors = [-1, -1] + [0] * (n - 1)\n",
    "        for i in range(2, n + 1):\n",
    "            if min_prime_factors[i] == 0:\n",
    "                primes.append(i)\n",
    "                min_prime_factors[i] = i\n",
    "            j = 0\n",
    "            while i * primes[j] <= n:\n",
    "                min_prime_factors[i * primes[j]] = primes[j]\n",
    "                if i % primes[j] == 0:\n",
    "                    break\n",
    "                j += 1\n",
    "        self._n = n\n",
    "        self._primes = primes\n",
    "        self._min_prime_factors = min_prime_factors\n",
    "\n",
    "    def _miller_rabin(self, m, seed):\n",
    "        assert m > 2 and (m & 1) == 1, '参数m不能设为%d' % m\n",
    "\n",
    "        k = 0\n",
    "        t = m - 1\n",
    "        while (t & 1) == 1:\n",
    "            t >>= 1\n",
    "            k += 1\n",
    "\n",
    "        a = pow(seed, t, m)\n",
    "        if a == 1 or a == m - 1:\n",
    "            return True\n",
    "        for i in range(k - 1):\n",
    "            a = pow(a, 2, m)\n",
    "            if a == 1:\n",
    "                return False\n",
    "            if a == m - 1:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def is_prime(self, m, k=10):\n",
    "        \"\"\"\n",
    "\n",
    "        Returns:\n",
    "            m是否为素数\n",
    "\n",
    "        Procedure:\n",
    "            1. 若m <= n，使用min_prime_factors直接判定，O(1)\n",
    "            2. 若m <= n * n或m存在n以内的素因子，遍历primes判定，O(len(primes))\n",
    "            3. 若m > n * n且m不存在n以内的素因子，miller_rabin随机算法判定，合数判成素数的错误率小于4^(-k)，O(len(primes) + k*log(n))\n",
    "\n",
    "        \"\"\"\n",
    "        if m <= self.n:\n",
    "            return self.min_prime_factors[m] == m\n",
    "        for p in self.primes:\n",
    "            if m % p == 0:\n",
    "                return False\n",
    "            if p * p > m:\n",
    "                return True\n",
    "        return all((self._miller_rabin(m, i) for i in self.primes[:k]))\n",
    "\n",
    "    def decompose(self, m):\n",
    "        \"\"\"正整数质因子分解\n",
    "\n",
    "        Returns:\n",
    "            [[p1, a1], [p2, a2] ...]，代表m = (p1 ^ a1) * (P2 ^ a2) * ...\n",
    "            举例：输入40，返回[[2, 3], [5, 1]]\n",
    "\n",
    "        Attention:\n",
    "            若m存在不只一个大于n的素因子，将命中断言，无法进一步分解\n",
    "\n",
    "        Time Complexity:\n",
    "            O(len(primes))\n",
    "\n",
    "        \"\"\"\n",
    "        assert m > 0, '参数m不能设为%d' % m\n",
    "\n",
    "        if m == 1:\n",
    "            return deque()\n",
    "        if m <= self.n:\n",
    "            t = self.min_prime_factors[m]\n",
    "            ans = self.decompose(m // t)\n",
    "            if ans and ans[0][0] == t:\n",
    "                ans[0][1] += 1\n",
    "            else:\n",
    "                ans.appendleft([t, 1])\n",
    "            return ans\n",
    "        ans = deque()\n",
    "        for p in self.primes:\n",
    "            if m % p == 0:\n",
    "                ans.append([p, 0])\n",
    "                while m % p == 0:\n",
    "                    ans[-1][1] += 1\n",
    "                    m //= p\n",
    "                if m == 1:\n",
    "                    return ans\n",
    "\n",
    "        assert self.is_prime(m), '%d存在不只一个大于n的素因子，无法进一步分解' % m\n",
    "        ans.append([m, 1])\n",
    "        return ans\n",
    "    \n",
    "p = Primer()\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, a: List[int]) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        for i, v in enumerate(a):\n",
    "            lt = []\n",
    "            for u, k in p.decompose(i + 1):\n",
    "                if k % 2 == 1:\n",
    "                    lt.append(u)\n",
    "            mp[tuple(lt)] += v\n",
    "        return max(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "a = [i**2 for i in range(1,10001)]\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        L = [0] * 10**5\n",
    "        n = len(nums)\n",
    "        for i in range(1,n+1):\n",
    "            for j in a:\n",
    "                if j*i >= n+1:break\n",
    "                L[i] += nums[j*i-1]\n",
    "        return max(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def core(n: int) -> int:\n",
    "    res = 1\n",
    "    for i in range(2, isqrt(n) + 1):\n",
    "        if n == 1:\n",
    "            break\n",
    "        e = 0\n",
    "        while n % i == 0:\n",
    "            e += 1\n",
    "            n //= i\n",
    "        print(e, n)\n",
    "        # e = n // i\n",
    "        # n -= e * i\n",
    "        if e % 2:\n",
    "            res *= i\n",
    "    if n > 1:\n",
    "        res *= n\n",
    "    return res\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            s[core(i + 1)] += x\n",
    "        print(s)\n",
    "        print(core(3), core(6), core(16))\n",
    "        return max(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n",
    "\n",
    "@cache\n",
    "def core(x):\n",
    "    if x == 1: return 1\n",
    "    for p in primes:\n",
    "        if x%p == 0:\n",
    "            res = core(x//p)\n",
    "            return res//p if res%p==0 else res*p\n",
    "    return x\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        score = Counter()\n",
    "        for i,n in enumerate(nums): score[core(i+1)] += n\n",
    "        return max(score.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def prime_factor(num: int) -> List[int]:\n",
    "            ans = Counter()\n",
    "            up = int(num ** 0.5 + 1)\n",
    "            for i in range(2, up):\n",
    "                while num % i == 0:\n",
    "                    num //= i\n",
    "                    ans[i] += 1\n",
    "            if num != 1:\n",
    "                ans[num] += 1\n",
    "            return ans\n",
    "        \n",
    "        ans = 0\n",
    "        cnts = collections.defaultdict(lambda:[])\n",
    "        \n",
    "        for idx, num in enumerate(nums):\n",
    "            keys = []\n",
    "            for k, v in prime_factor(idx + 1).items():\n",
    "                if v % 2 == 1:\n",
    "                    keys.append(k)\n",
    "            cnts[tuple(sorted(keys))].append(num)\n",
    "            if not keys:\n",
    "                ans += num\n",
    "                \n",
    "        ans = max(ans, max(nums))\n",
    "                \n",
    "        for _, arr in cnts.items():\n",
    "            ans = max(ans, sum(arr))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "\n",
    "pt=PrimeTable()\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums=[0]+nums\n",
    "        d=defaultdict(int)\n",
    "        for i,x in enumerate(nums):\n",
    "            if i<1:\n",
    "                continue\n",
    "            t=1\n",
    "            for p,c in pt.prime_factorization(i):\n",
    "                if c%2==1:\n",
    "                    t*=p\n",
    "            d[t]+=x\n",
    "        #print(d)\n",
    "        return max(d.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理\n",
    "def getCore(num):\n",
    "    d = 2\n",
    "    res = 1\n",
    "    while d < num:\n",
    "        cnt = 0\n",
    "        while num % d == 0:\n",
    "            num //= d\n",
    "            cnt += 1\n",
    "        if cnt&1:\n",
    "            res *= d\n",
    "        d += 1\n",
    "    # if num > 1:\n",
    "    res *= num\n",
    "    return res\n",
    "\n",
    "maxValue = int(1e4)\n",
    "        \n",
    "# 获取同一组对应的所有下标值\n",
    "group = defaultdict(list)\n",
    "for num in range(1,maxValue+1):    \n",
    "    group[getCore(num)].append(num)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历每个下标分组\n",
    "        for varr in group.values():\n",
    "            # 分组求和\n",
    "            t = 0\n",
    "            for i in varr:\n",
    "                if i > n:\n",
    "                    break\n",
    "                t += nums[i-1]\n",
    "            res = max(res,t)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# auther yeling\n",
    "from typing import List\n",
    "from bisect import *\n",
    "from collections import *\n",
    "from functools import *\n",
    "from itertools import *\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import Optional\n",
    "from heapq import *\n",
    "import string\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "INF = 2 ** 64 - 1\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    # 495 / 663 \n",
    "    # 556 / 663 \n",
    "    def maximumSum(self, nums: List[int]) -> int:    \n",
    "        n = len(nums)\n",
    "        # 一个数字处以 4 9 25 。。。 剩下来的值，\n",
    "        # 如果两个数字剩下来的相同，他们的乘积就是完全平方数\n",
    "        core = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            curr = i + 1\n",
    "            for j in range(2, int(sqrt(n)) + 1):\n",
    "                if curr < j:\n",
    "                    break\n",
    "                while curr % (j * j) == 0:\n",
    "                    curr //= (j * j)\n",
    "            core[curr].append(i)\n",
    "        # print(core)\n",
    "        ans = 0\n",
    "        for k in core:\n",
    "            temp = sum(nums[v] for v in core[k])\n",
    "            ans = max(ans, temp)\n",
    "\n",
    "\n",
    "        return ans\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(nums)\n",
    "        ret = []\n",
    "        for i in range(1, 10000):\n",
    "            cnt = 1\n",
    "            ret2 = []\n",
    "            gap = i\n",
    "            while gap * cnt ** 2 <= len1:\n",
    "                ret2.append(cnt ** 2 * gap)\n",
    "                cnt += 1\n",
    "            if len(ret2) == 0:\n",
    "                break\n",
    "            ret.append(ret2)\n",
    "        s1 = max(nums)\n",
    "        for i in ret:\n",
    "            v1 = 0\n",
    "            for x in i:\n",
    "                v1 += nums[x - 1]\n",
    "            s1 = max(s1, v1)\n",
    "        return s1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxValue = int(1e4)\n",
    "        \n",
    "# 获取[1, maxValue]内所有质数\n",
    "tmp = [1] * (maxValue + 1)        \n",
    "prime = []\n",
    "\n",
    "for i in range(2,maxValue + 1):\n",
    "    if tmp[i] == 1:\n",
    "        prime.append(i)\n",
    "\n",
    "    for j in prime:\n",
    "        if j*i > maxValue:\n",
    "            break\n",
    "\n",
    "        tmp[i*j] = 0\n",
    "\n",
    "        if i % j == 0:\n",
    "            break\n",
    "\n",
    "# 根据core分组\n",
    "group = defaultdict(list)\n",
    "# 质因数分解\n",
    "for num in range(1,maxValue+1):    \n",
    "    cur = num\n",
    "    tmp = 1\n",
    "    for p in prime:\n",
    "        cnt = 0\n",
    "        while num % p == 0:\n",
    "            cnt += 1\n",
    "            num //= p\n",
    "        if cnt&1:\n",
    "            tmp *= p\n",
    "        if num < p:\n",
    "            break\n",
    "    \n",
    "    group[tmp].append(cur)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历每个下标分组\n",
    "        for varr in group.values():\n",
    "            # 分组求和\n",
    "            t = 0\n",
    "            for i in varr:\n",
    "                if i > n:\n",
    "                    break\n",
    "                t += nums[i-1]\n",
    "            res = max(res,t)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Primer(object):\n",
    "    \"\"\"素数相关运算的辅助类\n",
    "\n",
    "    Attributes:\n",
    "        1. n：用素数筛选法提前计算好的最大数\n",
    "        2. primes：n以内的所有素数列表\n",
    "        3. min_prime_factors：每个下标数的最小素因数（最小素因数不存在时为-1）\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    @property\n",
    "    def n(self):\n",
    "        return self._n\n",
    "\n",
    "    @property\n",
    "    def primes(self):\n",
    "        return self._primes\n",
    "\n",
    "    @property\n",
    "    def min_prime_factors(self):\n",
    "        return self._min_prime_factors\n",
    "\n",
    "    def __init__(self, n=31625):\n",
    "        \"\"\"初始化\n",
    "\n",
    "        生成n以内的所有素数primes，同时得到每个数的最小素因数min_prime_factors\n",
    "\n",
    "        Time Complexity:\n",
    "            O(n)\n",
    "\n",
    "        \"\"\"\n",
    "        primes = []\n",
    "        min_prime_factors = [-1, -1] + [0] * (n - 1)\n",
    "        for i in range(2, n + 1):\n",
    "            if min_prime_factors[i] == 0:\n",
    "                primes.append(i)\n",
    "                min_prime_factors[i] = i\n",
    "            j = 0\n",
    "            while i * primes[j] <= n:\n",
    "                min_prime_factors[i * primes[j]] = primes[j]\n",
    "                if i % primes[j] == 0:\n",
    "                    break\n",
    "                j += 1\n",
    "        self._n = n\n",
    "        self._primes = primes\n",
    "        self._min_prime_factors = min_prime_factors\n",
    "\n",
    "    def _miller_rabin(self, m, seed):\n",
    "        assert m > 2 and (m & 1) == 1, '参数m不能设为%d' % m\n",
    "\n",
    "        k = 0\n",
    "        t = m - 1\n",
    "        while (t & 1) == 1:\n",
    "            t >>= 1\n",
    "            k += 1\n",
    "\n",
    "        a = pow(seed, t, m)\n",
    "        if a == 1 or a == m - 1:\n",
    "            return True\n",
    "        for i in range(k - 1):\n",
    "            a = pow(a, 2, m)\n",
    "            if a == 1:\n",
    "                return False\n",
    "            if a == m - 1:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def is_prime(self, m, k=10):\n",
    "        \"\"\"\n",
    "\n",
    "        Returns:\n",
    "            m是否为素数\n",
    "\n",
    "        Procedure:\n",
    "            1. 若m <= n，使用min_prime_factors直接判定，O(1)\n",
    "            2. 若m <= n * n或m存在n以内的素因子，遍历primes判定，O(len(primes))\n",
    "            3. 若m > n * n且m不存在n以内的素因子，miller_rabin随机算法判定，合数判成素数的错误率小于4^(-k)，O(len(primes) + k*log(n))\n",
    "\n",
    "        \"\"\"\n",
    "        if m <= self.n:\n",
    "            return self.min_prime_factors[m] == m\n",
    "        for p in self.primes:\n",
    "            if m % p == 0:\n",
    "                return False\n",
    "            if p * p > m:\n",
    "                return True\n",
    "        return all((self._miller_rabin(m, i) for i in self.primes[:k]))\n",
    "\n",
    "    def decompose(self, m):\n",
    "        \"\"\"正整数质因子分解\n",
    "\n",
    "        Returns:\n",
    "            [[p1, a1], [p2, a2] ...]，代表m = (p1 ^ a1) * (P2 ^ a2) * ...\n",
    "            举例：输入40，返回[[2, 3], [5, 1]]\n",
    "\n",
    "        Attention:\n",
    "            若m存在不只一个大于n的素因子，将命中断言，无法进一步分解\n",
    "\n",
    "        Time Complexity:\n",
    "            O(len(primes))\n",
    "\n",
    "        \"\"\"\n",
    "        assert m > 0, '参数m不能设为%d' % m\n",
    "\n",
    "        if m == 1:\n",
    "            return []\n",
    "        if m <= self.n:\n",
    "            t = self.min_prime_factors[m]\n",
    "            ans = self.decompose(m // t)\n",
    "            if ans and ans[-1][0] == t:\n",
    "                ans[-1][1] += 1\n",
    "            else:\n",
    "                ans.append([t, 1])\n",
    "            return ans\n",
    "        ans = []\n",
    "        for p in self.primes:\n",
    "            if m % p == 0:\n",
    "                ans.append([p, 0])\n",
    "                while m % p == 0:\n",
    "                    ans[-1][1] += 1\n",
    "                    m //= p\n",
    "                if m == 1:\n",
    "                    return ans\n",
    "\n",
    "        assert self.is_prime(m), '%d存在不只一个大于n的素因子，无法进一步分解' % m\n",
    "        ans.append([m, 1])\n",
    "        return ans\n",
    "    \n",
    "p = Primer()\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, a: List[int]) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        for i, v in enumerate(a):\n",
    "            lt = []\n",
    "            for u, k in p.decompose(i + 1):\n",
    "                if k % 2 == 1:\n",
    "                    lt.append(u)\n",
    "            mp[tuple(lt)] += v\n",
    "        return max(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n=len(nums)\n",
    "        cnt=defaultdict(list)\n",
    "        for i in range(1,n+1):\n",
    "            if int(i**0.5)**2==i:\n",
    "                cnt[(1)].append(i)\n",
    "                continue\n",
    "            \n",
    "            arr=[]\n",
    "            cur=i\n",
    "            for j in range(2,int(i**0.5)+1):\n",
    "                flag=0\n",
    "                while i%j==0:\n",
    "                    i//=j\n",
    "                    flag^=1\n",
    "                if flag:\n",
    "                    arr.append(j)\n",
    "            if i>1:arr.append(i)\n",
    "            # print(cur,arr)\n",
    "            cnt[tuple(arr)].append(cur)\n",
    "        \n",
    "        # print(cnt)\n",
    "        res=0\n",
    "        \n",
    "        for k,v in cnt.items():\n",
    "            s=sum(nums[i-1] for i in v)\n",
    "            res=max(res,s)\n",
    "        \n",
    "        return res\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(nums)\n",
    "        ret = []\n",
    "        for i in range(1, 1000000):\n",
    "            cnt = 1\n",
    "            ret2 = []\n",
    "            gap = i\n",
    "            while gap * cnt ** 2 <= len1:\n",
    "                ret2.append(cnt ** 2 * gap)\n",
    "                cnt += 1\n",
    "            if len(ret2) == 0:\n",
    "                break\n",
    "            ret.append(ret2)\n",
    "        s1 = max(nums)\n",
    "        for i in ret:\n",
    "            v1 = 0\n",
    "            for x in i:\n",
    "                v1 += nums[x - 1]\n",
    "            s1 = max(s1, v1)\n",
    "        return s1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        sqr = [i*i for i in range(1, 40000)]\n",
    "        for i in range(1, n+1):\n",
    "            tmp = 0\n",
    "            for x in sqr:\n",
    "                if x*i <= n:\n",
    "                    tmp += nums[i*x-1]\n",
    "                else:\n",
    "                    break\n",
    "            # print(i, tmp)\n",
    "            ans = max(ans, tmp)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    # T4\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]+nums.copy()\n",
    "        d = [i*i for i in range(2,n+10)]\n",
    "        @cache\n",
    "        def core(p :int)->int:\n",
    "            t = 0\n",
    "            while p >= d[t]:\n",
    "                while p % d[t] == 0:\n",
    "                    p //= d[t]\n",
    "                t += 1\n",
    "            return p\n",
    "        s = Counter()\n",
    "        for i,x in enumerate(nums,1):\n",
    "            s[core(i)] += x\n",
    "        return max(s.values())\n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "\n",
    "s = Solution()\n",
    "s.maximumSum([5,10,3,10,1,13,7,9,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = [0]+nums\n",
    "        idx =[]\n",
    "        p = []\n",
    "        for i in range(1,n+1):\n",
    "            if i*i<=n:p.append(i*i)\n",
    "        for i in range(1,n+1):\n",
    "            tmp = []\n",
    "            for a in p:\n",
    "                if a*i<=n:tmp.append(a*i)\n",
    "            if  tmp : idx.append(tmp)\n",
    "        mx = 0\n",
    "        for v in idx:\n",
    "            a = [nums[i] for i in v]\n",
    "            mx = max(mx,sum(a))\n",
    "        return mx\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        def prime_factor(x):\n",
    "            prime = True\n",
    "            for i in range(2, int(x**0.5) + 1):\n",
    "                if not x % i:\n",
    "                    res = prime_factor(x // i)\n",
    "                    res.append(i)\n",
    "                    prime = False\n",
    "                    break\n",
    "            if prime:\n",
    "                return [x]\n",
    "            return res\n",
    "        \n",
    "        n = len(nums)\n",
    "        arr = []\n",
    "        table = collections.defaultdict(list)\n",
    "        table[()].append(0)\n",
    "        for i in range(1, n):\n",
    "            tmp = prime_factor(i + 1)\n",
    "            distinct = []\n",
    "            j = 0\n",
    "            if len(tmp) > 1:\n",
    "                while j < len(tmp) - 1:\n",
    "                    if tmp[j] != tmp[j + 1]:\n",
    "                        distinct.append(tmp[j])\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        j += 2\n",
    "                if j == len(tmp) - 1:\n",
    "                    distinct.append(tmp[j])\n",
    "            else:\n",
    "                distinct = tmp\n",
    "            # print(tmp, distinct)\n",
    "            table[tuple(distinct)].append(i)\n",
    "        # print(table)\n",
    "        ans = 0\n",
    "        for each in nums:\n",
    "            ans = max(ans, each)\n",
    "        for k, v in table.items():\n",
    "            if len(v) == 1: continue\n",
    "            tmp = 0\n",
    "            for i in v:\n",
    "                tmp += nums[i]\n",
    "            ans = max(ans, tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "\n",
    "pt=PrimeTable()\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums=[0]+nums\n",
    "        d=defaultdict(int)\n",
    "        for i,x in enumerate(nums):\n",
    "            if i<1:\n",
    "                continue\n",
    "            t=[]\n",
    "            for p,c in pt.prime_factorization(i):\n",
    "                if c%2==1:\n",
    "                    t.append(p)\n",
    "            d[tuple(t)]+=x\n",
    "        #print(d)\n",
    "        return max(d.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理\n",
    "def getCore(num):\n",
    "    d = 2\n",
    "    res = 1\n",
    "    while d < num:\n",
    "        cnt = 0\n",
    "        while num % d == 0:\n",
    "            num //= d\n",
    "            cnt += 1\n",
    "        if cnt&1:\n",
    "            res *= d\n",
    "        d += 1\n",
    "    # if num > 1:\n",
    "    res *= num\n",
    "    return res\n",
    "\n",
    "maxValue = int(1e4)\n",
    "        \n",
    "# 获取同一组对应的所有下标值\n",
    "group = defaultdict(list)\n",
    "for num in range(1,maxValue+1):    \n",
    "    group[getCore(num)].append(num)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历每个下标分组\n",
    "        for varr in group.values():\n",
    "            # 分组求和\n",
    "            t = 0\n",
    "            for i in varr:\n",
    "                if i > n:\n",
    "                    break\n",
    "                t += nums[i-1]\n",
    "            res = max(res,t)\n",
    "        \n",
    "        return res# 预处理\n",
    "maxValue = int(1e4)\n",
    "        \n",
    "# 获取[1, maxValue]内所有质数\n",
    "tmp = [1] * (maxValue + 1)        \n",
    "prime = []\n",
    "\n",
    "for i in range(2,maxValue + 1):\n",
    "    if tmp[i] == 1:\n",
    "        prime.append(i)\n",
    "\n",
    "    for j in prime:\n",
    "        if j*i > maxValue:\n",
    "            break\n",
    "\n",
    "        tmp[i*j] = 0\n",
    "\n",
    "        if i % j == 0:\n",
    "            break\n",
    "\n",
    "# 根据core分组\n",
    "group = defaultdict(list)\n",
    "# 质因数分解\n",
    "for num in range(1,maxValue+1):    \n",
    "    cur = num\n",
    "    tmp = 1\n",
    "    for p in prime:\n",
    "        cnt = 0\n",
    "        while num % p == 0:\n",
    "            cnt += 1\n",
    "            num //= p\n",
    "        if cnt&1:\n",
    "            tmp *= p\n",
    "        if num < p:\n",
    "            break\n",
    "    \n",
    "    group[tmp].append(cur)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        # 遍历每个下标分组\n",
    "        for varr in group.values():\n",
    "            # 分组求和\n",
    "            t = 0\n",
    "            for i in varr:\n",
    "                if i > n:\n",
    "                    break\n",
    "                t += nums[i-1]\n",
    "            res = max(res,t)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        cubes=[]\n",
    "        d=defaultdict(list)\n",
    "        for i in range(1,n+1):\n",
    "            x=int(sqrt(i))\n",
    "            if x*x==i:\n",
    "                cubes.append(i)\n",
    "            else:\n",
    "                d[i].append(i)\n",
    "        ans=sum([nums[x-1] for x in cubes])\n",
    "        s=set(cubes)\n",
    "        for i in range(2,n+1):\n",
    "            if i in s:\n",
    "                continue\n",
    "            for c in cubes[1:]:\n",
    "                x=c*i\n",
    "                if x<=n:\n",
    "                    d[i].append(c*i)\n",
    "            ans=max(ans,sum([nums[x-1] for x in d[i]]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prim_result = self.pick_prim(n + 1)\n",
    "        result = 0\n",
    "        memory = {}\n",
    "        for i in range(1, n + 1):\n",
    "            if self.is_perfect_sqrt(i):\n",
    "                result += nums[i - 1]\n",
    "                continue\n",
    "            prim_str = self.find_sub(i, prim_result)\n",
    "            if prim_str not in memory:\n",
    "                memory[prim_str] = [i - 1]\n",
    "            else:\n",
    "                memory[prim_str].append(i - 1)\n",
    "        for list_value in memory.values():\n",
    "            sum = 0\n",
    "            for index in list_value:\n",
    "                sum += nums[index]\n",
    "            result = max(result, sum)\n",
    "        return result\n",
    "\n",
    "\n",
    "    def pick_prim(self,n):\n",
    "        result = []\n",
    "        is_prime = [True] * (n + 1)\n",
    "        is_prime[0] = is_prime[1] = False\n",
    "        for i in range(2, n + 1):\n",
    "            if is_prime[i]:\n",
    "                if i * i <= n:\n",
    "                    j = i * i\n",
    "                    while j <= n:\n",
    "                        is_prime[j] = False\n",
    "                        j = j + i\n",
    "        for i in range(len(is_prime)):\n",
    "            if is_prime[i]:\n",
    "                result.append(i)\n",
    "        return result\n",
    "\n",
    "\n",
    "    def is_perfect_sqrt(self, value):\n",
    "        sqrt = math.sqrt(value)\n",
    "        return sqrt.is_integer()\n",
    "\n",
    "\n",
    "    def find_sub(self, value, prim):\n",
    "        result = []\n",
    "        final = []\n",
    "        i = 0\n",
    "        while i < len(prim) and value >= prim[i]:\n",
    "            if value % prim[i] == 0:\n",
    "                result.append(prim[i])\n",
    "                value //= prim[i]\n",
    "            else:\n",
    "                i += 1\n",
    "        result = [-1] + result\n",
    "        i = 1\n",
    "        count = 0\n",
    "        while i < len(result):\n",
    "            if result[i] != result[i - 1]:\n",
    "                if count % 2 == 1:\n",
    "                    final.append(str(result[i - 1]))\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "            if i == len(result) - 1 and count % 2 == 1:\n",
    "                final.append(str(result[-1]))\n",
    "            i += 1\n",
    "        result = '+'.join(final)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        def getf(v):\n",
    "            m = 2\n",
    "            r = 1\n",
    "            while m * m <= v:\n",
    "                if v % m == 0:\n",
    "                    c = 0\n",
    "                    while v % m == 0:\n",
    "                        v //= m\n",
    "                        c += 1\n",
    "                    if c % 2 == 1: r *= m\n",
    "                m += 1\n",
    "            r *= v\n",
    "            return r        \n",
    "        \n",
    "        c = defaultdict(list)\n",
    "        for i in range(1, n+1): c[getf(i)].append(i-1)\n",
    "        ans = 0\n",
    "        for k in c:\n",
    "            s = 0\n",
    "            for i in c[k]:\n",
    "                s += nums[i]\n",
    "            ans = max(ans, s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(set)\n",
    "        l = len(nums)\n",
    "        for n in range(1,l+1):\n",
    "            m = n \n",
    "            i = 2\n",
    "            while i * i <= n:\n",
    "                if n % (i * i) == 0:\n",
    "                    n //= i * i \n",
    "                else:\n",
    "                    i += 1\n",
    "            d[n].add(m)\n",
    "        ans = 0\n",
    "        for s in d.values():\n",
    "            if len(s) > 0:\n",
    "                ans = max(ans,sum(nums[i-1] for i in s))\n",
    "        return ans \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def fj(N):\n",
    "    ret=0\n",
    "    i=2\n",
    "    while i*i <=N:\n",
    "        if N%i==0:\n",
    "            while N%i==0:\n",
    "                N//=i\n",
    "                ret^=(1<<i)\n",
    "        i+=1\n",
    "    if N!=1:\n",
    "        ret^=(1<<N)\n",
    "    return ret\n",
    "tt=[0,0]+[fj(i) for i in range(2,int(1e4+10))]\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        d=defaultdict(int)\n",
    "        ret=nums[0]\n",
    "        for i,v in enumerate(nums):\n",
    "            if i==0: continue\n",
    "            x=tt[i+1]\n",
    "            d[x]+=v\n",
    "            if int(math.sqrt(i+1))**2==(i+1):\n",
    "                ret=max(ret,d[x]+nums[0])\n",
    "            else:\n",
    "                ret=max(ret,d[x])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    p = []\n",
    "    st = [True for i in range(int(1e5 + 1))]\n",
    "\n",
    "    def getPrimes(self, n):\n",
    "        self.st[1] = False\n",
    "        for i in range(2, n + 1):\n",
    "            if self.st[i]:\n",
    "                self.p.append(i)\n",
    "            for j, prime in enumerate(self.p):\n",
    "                if i * prime > n:\n",
    "                    break\n",
    "                self.st[i * prime] = False\n",
    "                if i % prime == 0:\n",
    "                    break\n",
    "    \n",
    "    def getFactors(self, x):\n",
    "        r = int(sqrt(x))\n",
    "        f = []\n",
    "        for i in range(2, r + 1):\n",
    "            if x % i == 0:\n",
    "                cnt = 0\n",
    "                while x % i == 0:\n",
    "                    cnt += 1\n",
    "                    x /= i\n",
    "                if cnt % 2 != 0:\n",
    "                    f.append(i)\n",
    "        if x > 1:\n",
    "            f.append(x)\n",
    "        return tuple(f)\n",
    "\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        # 完全平方数和非完全平方数相乘肯定不是完全平方数，所以要么全选完全平方数，要么全选非完全平方数\n",
    "        # 所有的完全平方数下标都选上是一个候选答案\n",
    "        # 剩下的数只统计出现奇数次的素因子\n",
    "        # 两个数可以放在一起，当且仅当这两个数出现奇数次的素因子的种类完全一样\n",
    "        # 统计答案即可\n",
    "        if len(self.p) == 0:\n",
    "            self.getPrimes(int(1e5))\n",
    "        \n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            if i * i <= n:\n",
    "                res += nums[i * i - 1]\n",
    "        \n",
    "        ans2 = {}\n",
    "        for i in range(n):\n",
    "            j = i + 1\n",
    "            r = int(sqrt(j))\n",
    "            if r * r != j:\n",
    "                factors = self.getFactors(j)\n",
    "                if ans2.get(factors) != None:\n",
    "                    ans2[factors] += nums[i]\n",
    "                else:\n",
    "                    ans2[factors] = nums[i]\n",
    "        for key in ans2.keys():\n",
    "            res = max(res, ans2[key])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prim_result = self.pick_prim(n + 1)\n",
    "        result = 0\n",
    "        memory = {}\n",
    "        for i in range(1, n + 1):\n",
    "            if self.is_perfect_sqrt(i):\n",
    "                result += nums[i - 1]\n",
    "                continue\n",
    "            prim_str = self.find_sub(i, prim_result)\n",
    "            if prim_str not in memory:\n",
    "                memory[prim_str] = [i - 1]\n",
    "            else:\n",
    "                memory[prim_str].append(i - 1)\n",
    "        for list_value in memory.values():\n",
    "            sum = 0\n",
    "            for index in list_value:\n",
    "                sum += nums[index]\n",
    "            result = max(result, sum)\n",
    "        return result\n",
    "\n",
    "\n",
    "    def pick_prim(self,n):\n",
    "        result = []\n",
    "        is_prime = [True] * (n + 1)\n",
    "        is_prime[0] = is_prime[1] = False\n",
    "        for i in range(2, n + 1):\n",
    "            if is_prime[i]:\n",
    "                if i * i <= n:\n",
    "                    j = i * i\n",
    "                    while j <= n:\n",
    "                        is_prime[j] = False\n",
    "                        j = j + i\n",
    "        for i in range(len(is_prime)):\n",
    "            if is_prime[i]:\n",
    "                result.append(i)\n",
    "        return result\n",
    "\n",
    "\n",
    "    def is_perfect_sqrt(self, value):\n",
    "        sqrt = math.sqrt(value)\n",
    "        return sqrt.is_integer()\n",
    "\n",
    "\n",
    "    def find_sub(self, value, prim):\n",
    "        result = []\n",
    "        final = []\n",
    "        i = 0\n",
    "        while i < len(prim) and value >= prim[i]:\n",
    "            if value % prim[i] == 0:\n",
    "                result.append(prim[i])\n",
    "                value //= prim[i]\n",
    "            else:\n",
    "                i += 1\n",
    "        result = [-1] + result\n",
    "        i = 1\n",
    "        count = 0\n",
    "        while i < len(result):\n",
    "            if result[i] != result[i - 1]:\n",
    "                if count % 2 == 1:\n",
    "                    final.append(str(result[i - 1]))\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "            if i == len(result) - 1 and count % 2 == 1:\n",
    "                final.append(str(result[-1]))\n",
    "            i += 1\n",
    "        result = '+'.join(final)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prim_result = self.pick_prim(n + 1)\n",
    "        result = 0\n",
    "        memory = {}\n",
    "        for i in range(1, n + 1):\n",
    "            if self.is_perfect_sqrt(i):\n",
    "                result += nums[i - 1]\n",
    "                continue\n",
    "            prim_str = self.find_sub(i, prim_result)\n",
    "            if prim_str not in memory:\n",
    "                memory[prim_str] = [i - 1]\n",
    "            else:\n",
    "                memory[prim_str].append(i - 1)\n",
    "        for list_value in memory.values():\n",
    "            sum = 0\n",
    "            for index in list_value:\n",
    "                sum += nums[index]\n",
    "            result = max(result, sum)\n",
    "        return result\n",
    "\n",
    "\n",
    "    def pick_prim(self,n):\n",
    "        result = []\n",
    "        is_prime = [True] * (n + 1)\n",
    "        is_prime[0] = is_prime[1] = False\n",
    "        for i in range(2, n + 1):\n",
    "            if is_prime[i]:\n",
    "                if i * i <= n:\n",
    "                    j = i * i\n",
    "                    while j <= n:\n",
    "                        is_prime[j] = False\n",
    "                        j = j + i\n",
    "        for i in range(len(is_prime)):\n",
    "            if is_prime[i]:\n",
    "                result.append(i)\n",
    "        return result\n",
    "\n",
    "\n",
    "    def is_perfect_sqrt(self, value):\n",
    "        sqrt = math.sqrt(value)\n",
    "        return sqrt.is_integer()\n",
    "\n",
    "\n",
    "    def find_sub(self, value, prim):\n",
    "        result = []\n",
    "        final = []\n",
    "        i = 0\n",
    "        while i < len(prim) and value >= prim[i]:\n",
    "            if value % prim[i] == 0:\n",
    "                result.append(prim[i])\n",
    "                value //= prim[i]\n",
    "            else:\n",
    "                i += 1\n",
    "        result = [-1] + result\n",
    "        i = 1\n",
    "        count = 0\n",
    "        while i < len(result):\n",
    "            if result[i] != result[i - 1]:\n",
    "                if count % 2 == 1:\n",
    "                    final.append(str(result[i - 1]))\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "            if i == len(result) - 1 and count % 2 == 1:\n",
    "                final.append(str(result[-1]))\n",
    "            i += 1\n",
    "        result = '+'.join(final)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = [2]\n",
    "for i in range(3, 10001, 2):\n",
    "    if all(i % j for j in primes):\n",
    "        primes.append(i)\n",
    "\n",
    "groups = defaultdict(list)\n",
    "for i in range(1, 10001):\n",
    "    g = 0\n",
    "    ii = i\n",
    "    for j in primes:\n",
    "        k = 0\n",
    "        while ii % j == 0:\n",
    "            ii //= j\n",
    "            k += 1\n",
    "        g <<= 1\n",
    "        g |= k & 1\n",
    "    groups[g].append(i - 1)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        return max(\n",
    "            sum(nums[i] for i in takewhile(lambda i: i < len(nums), g))\n",
    "            for g in groups.values()\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        s=[]\n",
    "        \n",
    "        n=len(nums)\n",
    "        d={}\n",
    "        # lh=[1]\n",
    "        maxa=0\n",
    "        a=0\n",
    "        for j in range(1,n+1):\n",
    "            if j**2<=n:\n",
    "                a=a+nums[j**2-1]\n",
    "                s.append(j**2)\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            if i in s:\n",
    "                continue\n",
    "            d[i]=[i]\n",
    "            for j in range(2,int(sqrt((n/i)))+1):\n",
    "                if True:                                               \n",
    "                    if (i*j*j<=n):\n",
    "                        d[i].append(i*j*j)                    \n",
    "                        \n",
    "        ll=[]\n",
    "        for i in d:\n",
    "            \n",
    "            p=list(set(d[i]))\n",
    "            maxa=max(maxa,sum([nums[j-1]for j in p]))\n",
    "\n",
    "        maxa=max(maxa,a)     \n",
    "            \n",
    "        print(maxa,n,d,s,a)\n",
    "        return maxa\n",
    "               \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # res = defaultdict(list)\n",
    "        res = Counter()\n",
    "        for i in range(1, n+1):\n",
    "            demo = i\n",
    "            c = 1\n",
    "            for j in range(2, isqrt(n)+2):\n",
    "                times = 0\n",
    "                while i % j == 0:\n",
    "                    i //= j\n",
    "                    times += 1\n",
    "                if times % 2: c *= j\n",
    "            if i > 1: c *= i\n",
    "            res[demo] = c\n",
    "        ans = 0\n",
    "        print(res)\n",
    "        s = [0] * (n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            s[res[i+1]] += x\n",
    "        return max(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "cnt = [0]\n",
    "for i in range(2,10001):\n",
    "    tmp = 0\n",
    "    cur = i\n",
    "    for j in range(2,i + 1):\n",
    "        if cur == 1:\n",
    "            break\n",
    "        while cur % j == 0:\n",
    "            cur //= j\n",
    "            tmp ^= (1 << j)\n",
    "    cnt.append(tmp)\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        can = defaultdict(list)\n",
    "        can[0].append(nums[0])\n",
    "        for i in range(1,n):\n",
    "            can[cnt[i]].append(nums[i])\n",
    "        for v in can:\n",
    "            ans = max(ans,sum(can[v]))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # res = defaultdict(list)\n",
    "        res = Counter()\n",
    "        for i in range(1, n+1):\n",
    "            demo = i\n",
    "            c = 1\n",
    "            for j in range(2, isqrt(n)+1):\n",
    "                times = 0\n",
    "                while i % j == 0:\n",
    "                    i //= j\n",
    "                    times += 1\n",
    "                if times % 2: c *= j\n",
    "            if i > 1: c *= i\n",
    "            res[demo] = c\n",
    "        ans = 0\n",
    "        print(res)\n",
    "        s = [0] * (n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            s[res[i+1]] += x\n",
    "        return max(s)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
